This invention relates to an arithmetic processor, and more particularly, to a high-speed arithmetic processor having a regular cellular array structure which is suitable for and easily implemented into large scale integration (LSI) circuit devices and which incorporates means for performing high speed calculations by using a redundant signed-digit number representation when performing internal arithmetic operations.
Conventionally, an arithmetic processor which adds a plurality of numbers whose most significant digits are different in position from each other comprises an adder tree, for example, using a carry retaining adder which simultaneously adds three digits and obtains two calculated results as output, the thus-obtained results being further added to a next higher order digit in a similar manner for the purpose of obtaining a final sum. In many applications, two numbers are required to be added in a manner whereby the digits of the first number are offset from the digits of the second number. A common example is the addition of partial sums formed during a multiplication calculation. The digits of the two offset numbers may be considered to generally comprise three portions: a lower order portion, in which the lower order digits of one of the offset numbers are not overlapped by digits of the other number, an intermediate portion, in which there are digits of both numbers present, and a higher order portion in which higher order digits of only one number are present. In the prior art, addition of the two numbers is performed by making the lower order portion part of the sum, per se. The digits of the intermediate portion are added by standard methods. In the higher order portion, when either digits of only the first or the second number is present, the addition is performed by first extending the sign for negative numbers (which are represented in 2's complement binary form). Sign extension is necessary because the carry from the intermediate digits has to be properly considered.
In the above described prior art, in a case where digits of either the first number or the second number are not present in the higher order portion, it is necessary for the higher order portion to be added by sign extension. Therefore, an adder for this portion is additionally needed. Furthermore, when addition is performed on a plurality of numbers which have their most significant digits offset with respect to each other, a problem arises in that the regularity of the circuit can be lost since the sum is extended by one digit due to the carry from the most significant digit whenever an addition is performed.